This project question has template files in the repository. You’ll need to grab the assignment from the link below and download the entire folder to your computer before proceeding. I would highly suggest then opening the entire folder in VS Code, as it will make it very easy to edit the different files and is necessary for VS Code to find certain libraries. When you are finished, upload your completed templates back to GitHub. Don’t worry about changing any file names, you want to overwrite the original template files.

Project Title: Build Your Own Bag: A Custom Collection Class

Project Overview

You are tasked with designing and implementing a Bag (also known as a multiset) data structure in Python. A Bag is a collection where items can appear more than once, and the order of the items does not matter. Unlike a standard set, adding an item that is already in the Bag simply increases its count, rather than doing nothing. This project challenges you to apply your knowledge of fundamental data structures and object-oriented programming to create a robust and efficient custom collection class. A key constraint of this project is that you are not allowed to use any built-in methods of the internal Python collection you choose for implementation. You must build the logic for each method from scratch using basic Python types, loops, and conditional statements.

Learning Goals

Understand the concept of a Bag/Multiset: Grasp the core properties and behaviors of a collection that allows duplicates and is unordered.
Practice Object-Oriented Programming (OOP): Implement a class with methods that encapsulate behavior and data, and understand the role of “dunder” (double underscore) methods.
Explore Trade-offs in Data Structure Design: Analyze the time and space complexity of different internal storage options and justify your choice.
Develop Problem-Solving and Testing Skills: Write clear, concise, and comprehensive tests to ensure your implementation is correct and handles edge cases.
Analyze and Reflect: Articulate your design decisions and relate your data structure to real-world applications.

Requirements

Part 1: The Bag Class

Implement a class named Bag that adheres to the following specifications. Your implementation must be in a single Python file, bag.py.

Student Choice (Internal Data Structure)

You must choose one of Python’s built-in collections (list or dict) to store the items inside your Bag class. For example, if you choose a list, your Bag object would have a member variable like self._items = []. If you choose a dict, you might have self._counts = {}.

Important Constraint: You are not allowed to use any built-in methods of your chosen internal data structure that would directly solve the problem for you. For example, if you choose a list, you cannot use list.count(), list.remove(), or len(list). If you choose a dict, you cannot use dict.get(), dict.keys(), or len(dict). You must implement the logic for each required method using basic loops and control flow.

Core Methods

__init__(self, iterable=None):
- Initializes an empty Bag.
- Optionally accepts an iterable (e.g., a list or a tuple) to initialize the Bag with a set of starting items.
  Example: Bag([1, 2, 2, 3]) should create a bag with these items.
add(self, item):
- Adds one occurrence of an item to the Bag.
- If the item is already present, its count is incremented.
remove(self, item):
- Removes one occurrence of an item from the Bag.
- If the item is not present in the Bag, raise a ValueError with a clear and informative message (e.g., “Item not found in the Bag”).
count(self, item):
- Returns the number of times an item appears in the Bag.
- If the item is not in the bag, it should return 0.

Dunder (Magic) Methods for Standard Python Behavior

__len__(self):
- Returns the total number of items in the Bag (including duplicates).
- Example: If the Bag contains [1, 2, 2, 3], len(my_bag) should return 4.
__iter__(self):
- Allows the Bag to be iterable, meaning you can loop through all items.
- The iteration should yield each item, including all of its duplicates. The order of yielded items does not matter.
- Example: for item in my_bag: print(item) should print all items in the Bag.
__contains__(self, item):
- Enables the use of the in operator to check for membership.
- Returns True if the item is in the Bag (at least one occurrence), and False otherwise.
__repr__(self):
- Provides a string representation of the Bag for developers.
- Should return a string that could be used to recreate the object. A format like Bag({1: 2, 2: 1}) is a good example, showing the counts of each unique item.

Part 2: Design and Analysis

Justification:
You must provide a clear justification for your chosen internal data structure (list or dict) in a short section of comments or a separate text file named design_choices.md.

Your justification should include an analysis of the time complexity for the key operations (add, remove, count, __len__, __contains__) for both your chosen data structure and the alternative. For example, if you choose a dict, analyze its complexity and then compare it to the complexity of a list-based implementation.

Part 3: Testing

Create a separate file named test_bag.py.

Write a comprehensive set of tests to ensure your Bag class works correctly. Your tests should cover:

Basic functionality (add, remove, count)
The __len__, __iter__, and __contains__ methods
Edge cases:
- Removing the last occurrence of an item
- Attempting to remove an item that is not in the Bag (and confirming the ValueError is raised)
- Initializing the Bag with an empty iterable or no iterable
- Adding different data types (e.g., strings, numbers)

Part 4: Reflection

Write a paragraph (150-250 words) in a separate file named reflection.md that addresses the following:

Design Rationale: Explain your primary design choices in simple terms.
Real-World Use Cases: Describe two or three real-world scenarios where a Bag data structure would be a more suitable choice than a standard list, set, or dictionary.
Future Improvements: Suggest one or two additional features or methods that would enhance the functionality of your Bag class (e.g., a method to find the most frequent item, a way to combine two bags).

Submission

Your submission should include the following files:

bag.py (The implementation of your Bag class)
test_bag.py (Your test suite)
design_choices.md (Your justification for your data structure choice)
reflection.md (Your reflection paragraph)

This structure provides a clear path for students to not only write code but also to think critically about their design, analyze its performance, and communicate their reasoning effectively. It transforms a simple coding exercise into a full-fledged mini-project in data structure design.